package stu.day25_day32.day29;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class hw1 {


    List<List<Integer>> list = new ArrayList<>();
    List<Integer> arr = new ArrayList<>();
    HashSet<Integer> set = new HashSet<>();


    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack2(candidates,target,0,0);
        return list;
    }

    public void backtrack2(int[] candiates,int target,int sum,int index){
        if(sum==target){
            list.add(new ArrayList<>(arr));
        }
        if(sum>target){
            return;
        }

        for(int i=index;i<candiates.length;i++){
            if(i>index && candiates[i]==candiates[i-1]){
                continue;
            }
            arr.add(candiates[i]);
            backtrack2(candiates,target,sum+candiates[i],i+1);
            arr.removeLast();
        }

    }







    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        backtrack1(candidates,target,0,0);
        return list;

    }
    public void backtrack1(int[] candiates,int target,int sum,int index){
        if(sum==target){
            list.add(new ArrayList<>(arr));
        }
        if(sum>target){
            return;
        }

        for(int i=index;i<candiates.length;i++){
            arr.add(candiates[i]);
            backtrack1(candiates,target,sum+candiates[i],index);
            arr.removeLast();
        }

    }



}
